#
# @lc app=leetcode.cn id=22 lang=python3
#
# [22] 括号生成
#
# https://leetcode-cn.com/problems/generate-parentheses/description/
#
# algorithms
# Medium (75.83%)
# Likes:    1203
# Dislikes: 0
# Total Accepted:    156.5K
# Total Submissions: 206.2K
# Testcase Example:  '3'
#
# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
#
#
#
# 示例：
#
# 输入：n = 3
# 输出：[
# ⁠      "((()))",
# ⁠      "(()())",
# ⁠      "(())()",
# ⁠      "()(())",
# ⁠      "()()()"
# ⁠    ]
#
#
#

from typing import List

# @lc code=start


class Solution:
    '''
    41 ms
    '''

    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []

        self.max = n
        self.results = []

        self.generate("", 0, 0)

        return self.results

    def generate(self, current: str, left: int, right: int):
        if len(current) == self.max * 2:
            self.results.append(current)
            return

        if left < self.max:
            self.generate(current + "(", left + 1, right)
        if right < left:
            self.generate(current + ")", left, right + 1)

# @lc code=end


solution = Solution()
print(solution.generateParenthesis(3))

# class Solution:
#     '''
#     56 ms
#     '''

#     def generateParenthesis(self, n: int) -> List[str]:
#         if n == 0:
#             return []
#         if n == 1:
#             return ["()"]

#         results = set()

#         if n > 1:
#             for subResult in self.generateParenthesis(n - 1):
#                 results.add("(" + subResult + ")")

#         for i in range(1, n):
#             for ri in self.generateParenthesis(i):
#                 for rj in self.generateParenthesis(n - i):
#                     results.add(ri + rj)

#         return list(results)

# class Solution:
#     '''
#     46 ms
#     '''

#     def generateParenthesis(self, n: int) -> List[str]:
#         if n == 0:
#             return [""]
#         if n == 1:
#             return ["()"]

#         results = []

#         for i in range(0, n):
#             for ri in self.generateParenthesis(i):
#                 for rj in self.generateParenthesis(n - 1 - i):
#                     results.append("(" + ri + ")" + rj)

#         return results
